# based on utf-8
# author:2012190218,WangChenghua
# a example for QuickSort
# gitee:https://gitee.com/wangchsoft/hdoj

array_test = Array.new
index = 0
while index < 64
  array_test[index] = rand(100)
  index += 1
end
puts "The original is: " + array_test.to_s

def Part_QuickSort(array_in,first,last)
  x = array_in[last]
  i = first-1
  (first ..(last-1)).each do |k|
    if array_in[k] <= x
      i+=1
      array_in[i],array_in[k]=array_in[k],array_in[i]
    end
  end
  array_in[i+1],array_in[last]=array_in[last],array_in[i+1]
  return i+1
end

def QuickSort(array_in,first,last)
  if first < last
    middle = Part_QuickSort(array_in,first,last)
    QuickSort(array_in,first,middle-1)
    QuickSort(array_in,middle+1,last)
  end
end

QuickSort(array_test,0,array_test.length-1)
puts "After sort is: " + array_test.to_s
